package Top_Interview_Questions_Review._008Two_Pointers;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/11 12:58
 * <p>
 * 功能描述:
 */
public class _0287 {

    public static void main(String[] args) {
        _0287 test = new _0287();
        int[] nums = {1, 6, 7, 3, 4, 2, 6, 5};
        test.findDuplicate(nums);
    }

    /**
     * https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-si-lu-ji-dai-ma-python-by-liweiwei1419/
     * 二分法
     */
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int left = 1;
        int right = len - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;

            int cnt = 0;
            for (int num : nums) {
                if (num <= mid) {
                    cnt += 1;
                }
            }

            // 根据抽屉原理，小于等于 4 的个数如果严格大于 4 个
            // 此时重复元素一定出现在 [1, 4] 区间里

            if (cnt > mid) {
                // 重复元素位于区间 [left, mid]
                right = mid;
            } else {
                // if 分析正确了以后，else 搜索的区间就是 if 的反面
                // [mid + 1, right]
                left = mid + 1;
            }
        }
        return left;
    }

}
